package com.congee02;

public class RemoveNodes_Stack {

    ListNode[] sta = new ListNode[100005];
    int top = -1;

    public ListNode removeNodes(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        // 单调栈 sentinel, 最大或最小值
        final ListNode sentinel = new ListNode(Integer.MAX_VALUE, head);

        sta[++ top] = sentinel;
        ListNode p =head;
        while (p != null) {
            ListNode step = p.next;
            while (sta[top].val <= p.val) {
                top --;
            }
            sta[top].next = p;
            sta[++ top] = p;
            p = step;
        }

        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode composed = LeetcodeUtils.compose(5,2,13,3,8);
        ListNode ret = new RemoveNodes_Stack().removeNodes(composed);
        System.out.println(LeetcodeUtils.toList(ret));
    }

}
